package com.js.study.datastructs.hash;


import java.sql.PreparedStatement;

/**
 * @Author JiangSen
 * @DATE 2023/12/28 10:27
 */
public class MyHashTable<K,V> {
    private static class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;
        //内部类的构造函数
        public Node(K key, V value, Node<K,V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
        //tostring  方法展示 内容

        @Override
        public String toString() {
            StringBuffer stringBuffer = new StringBuffer();
            stringBuffer.append("[");
            Node<K,V> current = this;
            while(current !=null){
                stringBuffer.append("(").append(current.key).append(":").append(current.value).append(")->");
                current = current.next;
            }

            stringBuffer.append("null]");
            return stringBuffer.toString();
        }
    }

    private static final int DEFAULT_INITIAL_CAPACITY =1 << 4; //默认初始长度, 16
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认负载因子
    private Node<K,V>[] array;
    private int size;
    //constructor
    public MyHashTable(){
        this.array = new Node[DEFAULT_INITIAL_CAPACITY];
        this.size = 0;
    }
    //operation
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    //add  update
    public void put(K key,V value){
        int index = hash(key,array.length);
        System.out.println("index="+index);
        Node<K,V> current = array[index];
        //如果计算过的hash 地址已经存在数据, 判断是否同一个key ,如果key一样,用户进行了
        //  重新赋值操作, 直接对value 进行覆盖.
        while(current != null){
            if(current.key.equals(key)){
                current.value = value;
                return;
            }
            //指针 指向下一个位置.
            current = current.next;
        }
        //首次新建 找到下标  存放数据
        Node<K,V> kvNode = new Node<>(key,value,array[index]);
        array[index] = kvNode;
        size++;
        //冲突,多个数据存链表
        if((float) size/ array.length > DEFAULT_LOAD_FACTOR){
            grow();
            System.out.println("扩容后容量"+array.length);
        }
    }
    //自定义哈希函数, 计算key 对应的数组的索引值
    //hasgcode 计算返回可能为负数, 对int最大值进行与运算, 保证结果为一个正数
    //再模除长度取余  得到下标
    private int hash(K key, int length){
        return(key.hashCode() & Integer.MAX_VALUE)%length;
    }
    //扩容函数
    private void grow(){
        Node<K,V>[] newArray = new Node[array.length*2];

        for(int i= 0;i<array.length;i++){
            Node<K,V> current = array[i];
            while(current != null){
                int newIndex = hash(current.key,newArray.length);
                Node<K,V> nextNode = current.next;
                current.next = newArray[newIndex];
                newArray[newIndex] = current;
                current = nextNode;
            }
        }
        this.array = newArray;
    }
    //delete
    public V remove(K key){
        V result = null;
        int index = hash(key,array.length);
        Node<K,V> current = array[index];
        if(current == null){
            throw new RuntimeException(key+"对应的节点为空,无法删除");
        }
        if(current.key.equals(key)){
            result = current.value;
            array[index] = current.next;
            current.next = null;
            size--;
        }else{
            Node<K,V> prev = current;
            while(prev.next !=null){
                if(prev.next.key.equals(key)){
                    Node<K,V> delete = prev.next;
                    result = delete.value;
                    prev.next = prev.next.next;
                    delete.next = null;
                    size--;
                    break;
                }
                prev = prev.next;
            }
        }
        return result;
    }

    //select
    public V get(K key){
        int index = hash(key,array.length);
        Node<K,V> current = array[index];
        while(current != null){
            if(current.key.equals(key)){
                return current.value;
            }
            current = current.next;
        }
        return null;
    }
    public V get2(K key) {
        int index = hash(key, array.length);
        for (Node<K, V> currentNode = array[index]; currentNode != null; currentNode = currentNode.next) {
            if (currentNode.key.equals(key)) {
                return currentNode.value;
            }
        }
        return null;
    }


    public static void main(String[] args) {
        MyHashTable<String, String> test = new MyHashTable<>();
//        test.put("AA", "a");
//        test.put("BB", "b");
//        test.put("CC", "c");
//        test.put("XYZ", "abcd");
//        test.put("DD","dd");
//
//        System.out.println("array.length: "+test.array.length);
//        System.out.println("test.size: "+test.size);

//        System.out.println("get(AA) "+test.get("AA")+"\t"+test.get2("AA"));
//        System.out.println("get(CC) "+test.get("CC")+"\t"+test.get2("CC"));

//                System.out.println("测试删除CC这个key--开始");
//        System.out.println(test.remove("CC"));
//        System.out.println("get(CC) "+test.get("CC"));
//        System.out.println("测试删除CC这个key--结束ok");
//        System.out.println("array[0]: " + test.array[0]);
//        System.out.println("array[1]: " + test.array[1]);
//        System.out.println("array[9]: " + test.array[9]);
//        for (int i = 0; i < test.array.length; i++) {
//            if (test.array[i] != null) {
//                System.out.println("当前槽位：" + i + " " + test.array[i].key + "\t" + test.array[i].value + "\t" + test.array[i]);
//            } else {
//                System.out.println("这个槽位：" + i + " 没有值 ");
//            }
//        }
        for (int i = 1; i <= 18; i++) {
            test.put("" + i, "" + i);
        }
        System.out.println("array.length: " + test.array.length);
        System.out.println("test.size: " + test.size);
        for (int i = 0; i < test.array.length; i++) {
            if (test.array[i] != null) {
                System.out.println("当前槽位：" + i + " " + test.array[i].key + "\t" + test.array[i].value + "\t" + test.array[i]);
            } else {
                System.out.println("这个槽位：" + i + " 没有值 ");
            }
        }

    }

}
